package com.bm;

/**
 * Description: BM68 矩阵的最小路径和
 *
 * @author weiruibai.vendor
 * Date: 2022/10/20 10:19
 */
public class BM68 {

    public static void main(String[] args) {

        int[][] matrix = {{1, 3, 5, 9}, {8, 1, 3, 4}, {5, 0, 6, 1}, {8, 8, 4, 0}};

        matrix = new int[][]{{1, 2, 3}, {1, 2, 3}};
        System.out.println(minPathSum(matrix));
        System.out.println(minPathSum_dp(matrix));
    }

    public static int minPathSum_dp(int[][] matrix) {
        int N = matrix.length;
        int M = matrix[0].length;
        int[][] dp = new int[N][M];
        dp[0][0] = matrix[0][0];
        for (int i = 1; i < N; i++) {
            dp[0][i] = dp[0][i - 1] + matrix[0][i];
        }
        for (int i = 1; i < M; i++) {
            dp[i][0] = dp[i - 1][0] + matrix[i][0];
        }
        for (int i = 1; i < N; i++) {
            for (int j = 1; j < M; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j];
            }
        }
        return dp[N - 1][M - 1];
    }

    public static int minPathSum(int[][] matrix) {
        int ans = process(matrix, 0, 0, 0);
        return ans;
    }

    private static int process(int[][] matrix, int i, int j, int sum) {
        /*if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length) {
            return sum;
        }*/

        if (i == matrix.length - 1 && j == matrix[0].length - 1) {
            return sum + matrix[i][j];
        }
        Integer v1 = null;
        // 右
        if (j + 1 < matrix[0].length) {
            v1 = process(matrix, i, j + 1, sum + matrix[i][j]);
        }
        // 下
        Integer v2 = null;
        if (i + 1 < matrix.length) {
            v2 = process(matrix, i + 1, j, sum + matrix[i][j]);
        }
        return Math.min(v1 == null ? Integer.MAX_VALUE : v1, v2 == null ? Integer.MAX_VALUE : v2);
    }
}
